#include "heap.h"
void HeapInit(HP* php)
{
    assert(php);
    php->a = (HPTypeDate*)malloc(sizeof(HPTypeDate) * 4);
    if (php->a == NULL)
    {
        perror("malloc fail");
        return;
    }
    php->size = 0;
    php->capacity = 4;
}
void HeapPrint(HP* php, HPTypeDate n)
{
    assert(php);
    HPTypeDate* p = php->a;
    for (int i = 0;i < n;i++)
    {
        printf("%d ", p[i]);
    }
    printf("\n");
}
void swap(HPTypeDate* a, HPTypeDate* b)
{
    int p = *b;
    *b = *a;
    *a = p;
}
void Adjustup(HPTypeDate* a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] > a[parent])
        {
            swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}
void HeapPush(HP* php, HPTypeDate x)
{
    assert(php);
    if (php->capacity == php->size)
    {
        HPTypeDate* tmp = (HPTypeDate*)realloc(php->a, sizeof(HPTypeDate) * (php->capacity) * 2);
        if (tmp == NULL)
        {
            perror("realloc");
            return;
        }
        php->a = tmp;
        php->capacity *= 2;
    }

    php->a[php->size++] = x;
    Adjustup(php->a, php->size - 1);
}
bool HPEmpty(HP* php)
{
    return php->size == 0;
}
HPTypeDate HPTop(HP* php)
{
    assert(php);
    return php->a[0];
}
void Adjustdown(HPTypeDate* a,HPTypeDate n, HPTypeDate parent)
{
    HPTypeDate child = parent * 2+1;
    while (child < n)
    {
        if (child+1<n&&a[child] < a[child + 1])
        {
            child = child + 1;
        }
        if (a[parent] > a[child])
        {
            swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else 
            break;
    }
}
void HPPop(HP* php)
{
    assert(php);
    if (HPEmpty(php)) return;
    swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;
    Adjustdown(php->a, php->size,0);
}
